use priority_queue::PriorityQueue;
use rstar::{PointDistance, RTree, AABB};
use rustc_hash::FxHashMap;
use lru::LruCache;
use std::{f64::consts::PI, hash::{Hash, Hasher}, num::NonZeroUsize};
use std::borrow::Cow;

const MIN_ANGLE: f64 = 15.0f64.to_radians();
const MAX_ANGLE: f64 = 165.0f64.to_radians();
const SAFETY_MARGIN: f64 = 0.1;

use crate::{
    mash_data::{AABBObject, Edge, F64Point, NapiNavMeshData, NavMeshData},
};

#[derive(Debug, Clone, Copy)]
struct EqF64(i64, i64);

impl EqF64 {
    fn new(x: f64, y: f64) -> Self {
        // 将浮点数转换为整数，保留4位小数精度
        Self(
            (x * 10000.0).round() as i64,
            (y * 10000.0).round() as i64
        )
    }

    fn to_f64(&self) -> (f64, f64) {
        (
            self.0 as f64 / 10000.0,
            self.1 as f64 / 10000.0
        )
    }
}

impl Hash for EqF64 {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
        self.1.hash(state);
    }
}

impl PartialEq for EqF64 {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0 && self.1 == other.1
    }
}

impl Eq for EqF64 {}

impl PartialOrd for EqF64 {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for EqF64 {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        match self.0.cmp(&other.0) {
            std::cmp::Ordering::Equal => self.1.cmp(&other.1),
            ord => ord
        }
    }
}

impl From<f64> for EqF64 {
    fn from(value: f64) -> Self {
        Self(
            (value * 10000.0).round() as i64,
            (value * 10000.0).round() as i64
        )
    }
}

pub struct NavMesh {
    data: NavMeshData,
    pub rtree: RTree<AABBObject>,
    pub cache_portals: FxHashMap<(usize, usize), Edge>,
}

impl NavMesh {
    pub fn get_path_smooth(&self, start_x: f64, start_y:f64, end_x:f64, end_y:f64) -> Option<Vec<F64Point>> {
        let start = F64Point::new(start_x, start_y);
        let end = F64Point::new(end_x, end_y);
        self.search_path_smooth(&start, &end)
    }

    pub fn get_path(&self, start_x: f64, start_y:f64, end_x:f64, end_y:f64) -> Option<Vec<F64Point>> {
        let start = F64Point::new(start_x, start_y);
        let end = F64Point::new(end_x, end_y);
        self.search_path(&start, &end)
    }

    pub fn get_nearest_valid_point(&self, point_x:f64, point_y:f64) -> Option<F64Point> {
        let point = F64Point::new(point_x, point_y);
        self.search_nearest_valid_point(&point)
    }

    pub fn is_point_in_walkable_polygon(&self, point_x:f64, point_y:f64) -> bool {
        let point = F64Point::new(point_x, point_y);
        self.get_polygon_at_point(&point).is_some()
    }

    pub fn get_polygon_index_at_point(&self, point_x:f64, point_y:f64) -> Option<i32> {
        let point = F64Point::new(point_x, point_y);
        let Some(polygon_id) = self.get_polygon_at_point(&point) else {
            return None;
        };
        let Some(polygon_info) = self.data.polygons.get(polygon_id) else {
            return None;
        };
        Some(polygon_info.polygon_index as i32)
    }

    pub fn get_path_with_radius(&self, start_x: f64, start_y: f64, end_x: f64, end_y: f64, radius: f64, corner_points: usize) -> Option<Vec<F64Point>> {
        let start = F64Point::new(start_x, start_y);
        let end = F64Point::new(end_x, end_y);
        self.search_path_with_radius(&start, &end, radius, corner_points)
    }
}

#[cfg(feature = "napi")]
impl NavMesh {
    pub fn from_napi_data(data: NapiNavMeshData) -> Self {
        Self::new(data.into())
    }
}

impl NavMesh {

    pub fn from_json(str: &str) -> Option<Self> {
        let Some(data) = NavMeshData::from_json(str) else {
            return None;
        };
        Some(Self::new(data))
    }

    pub fn get_walkable_polygon_edges(&self)->Vec<Edge> {
        self.data.get_walkable_polygon_edges()
    }

    fn search_nearest_valid_point(&self, point: &F64Point) -> Option<F64Point> {
        let nearest_aabbs = self.rtree.nearest_neighbors(point);
        let mut result: Option<(F64Point, f64)> = None;

        for aabb in nearest_aabbs {
            let polygon = aabb.id;
            let polygon_data = match self.data.polygons.get(polygon) {
                Some(data) => data,
                None => continue, // 跳过无效多边形
            };

            let points: Vec<F64Point> = polygon_data
                .point_indices
                .iter()
                .filter_map(|&point_index| self.data.points.get(point_index))
                .cloned()
                .collect();

            if points.len() < 3 {
                continue; // 跳过点数小于 3 的多边形
            }

            let check_result = get_nearest_point_in_convex_polygon(point, &points);

            if f64_eq(check_result.1, 0f64) {
                return Some(check_result.0); // 找到点在多边形内，直接返回
            }

            result = match result {
                Some((_, dist)) if dist > check_result.1 => Some(check_result),
                None => Some(check_result),
                _ => result,
            };
        }

        result.map(|res| res.0)
    }

    fn get_portals(&self, paths: &[usize], start: &F64Point, end: &F64Point) -> Vec<Edge> {
        let mut portals: Vec<Edge> = Vec::new();
        portals.push((start.to_owned(), start.to_owned()));
        for index in 0..paths.len() - 1 {
            let Some(aindex) = paths.get(index) else {
                continue;
            };
            let Some(bindex) = paths.get(index + 1) else {
                continue;
            };
            let Some(edge) = self.get_shared_edge(*aindex, *bindex) else {
                continue;
            };
            portals.push(edge);
        }
        portals.push((end.to_owned(), end.to_owned()));
        portals
    }

    pub fn search_path_smooth(&self, start: &F64Point, end: &F64Point) -> Option<Vec<F64Point>> {
        let start_polygon = self.get_polygon_at_point(start)?;
        // let end = self.search_nearest_valid_point(end)?;
        let end_polygon = self.get_polygon_at_point(&end)?;
        let paths = self.astar_search(start_polygon, end_polygon)?;
        let portals = self.get_portals(&paths, start, &end);
        let path = self.funnel(&portals);
        Some(path)
    }

    pub fn search_path(&self, start: &F64Point, end: &F64Point) -> Option<Vec<F64Point>> {
        let start_polygon = self.get_polygon_at_point(start)?;
        let end_point = self.search_nearest_valid_point(end)?;
        let end_polygon = self.get_polygon_at_point(&end_point)?;
        let polygons = self.astar_search(start_polygon, end_polygon)?;
        let mut result: Vec<F64Point> = polygons
            .iter()
            .filter_map(|&polygon_index| self.data.get_polygon_center_pos(polygon_index))
            .collect();
        result.push(end_point);
        Some(result)
    }

    fn new(data: NavMeshData) -> Self {
        let rtree = RTree::bulk_load(data.gen_aabb_objects());
        let cache_portals = data.gen_portals();
        Self {
            data,
            rtree,
            cache_portals,
        }
    }

    fn get_shared_edge(&self, aindex: usize, bindex: usize) -> Option<Edge> {
        self.cache_portals.get(&(bindex, aindex)).copied()
    }

    pub  fn get_polygon_at_point(&self, point: &F64Point) -> Option<usize> {
        let search_aabb = AABB::from_point(point.to_owned());
        let aabbs = self.rtree.locate_in_envelope_intersecting(&search_aabb);
        for aabb in aabbs {
            if self.data.polygon_contains_point(aabb.id, point) {
                return Some(aabb.id);
            }
        }
        None
    }

    fn reconstruct_path(
        &self,
        came_from: &FxHashMap<usize, usize>,
        start: usize,
        goal: usize,
    ) -> Vec<usize> {
        let mut current = goal;
        let mut path = vec![current];
        while current != start {
            match came_from.get(&current) {
                Some(&prev) => {
                    path.push(prev);
                    current = prev;
                }
                None => break,
            }
        }
        path.reverse();
        path
    }

    fn astar_search(&self, start: usize, goal: usize) -> Option<Vec<usize>> {
        let mut open_set: PriorityQueue<usize, EqF64> = PriorityQueue::new();
        open_set.push(start, 0.0.into());

        let mut came_from = FxHashMap::default();
        let mut g_score = FxHashMap::default();
        g_score.insert(start, 0.0);

        let mut f_score = FxHashMap::default();
        f_score.insert(start, self.data.polygon_manhattan_dist(start, goal));

        while let Some((current, _)) = open_set.pop() {
            if current == goal {
                return Some(self.reconstruct_path(&came_from, start, goal));
            }

            if let Some(neighbors) = self.data.neighbors.get(current) {
                for &neighbor in neighbors.iter() {
                    let tentative_g_score =
                        g_score[&current] + self.data.polygon_manhattan_dist(current, neighbor);

                    if tentative_g_score < *g_score.get(&neighbor).unwrap_or(&f64::INFINITY) {
                        let h_score = self.data.polygon_manhattan_dist(neighbor, goal);
                        came_from.insert(neighbor, current);
                        g_score.insert(neighbor, tentative_g_score);
                        f_score.insert(neighbor, tentative_g_score + h_score);

                        open_set.push(neighbor, (-(tentative_g_score + h_score)).into());
                    }
                }
            }
        }
        None
    }

    fn triangle_area2(a: &F64Point, b: &F64Point, c: &F64Point) -> f64 {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    }

    fn funnel(&self, portals: &[Edge]) -> Vec<F64Point> {
        if portals.is_empty() {
            return Vec::new();
        }

        let mut path: Vec<F64Point> = Vec::new();
        let mut left_index = 0;
        let mut right_index = 0;

        let mut portal_apex = &portals[0].0;
        let mut portal_left = &portals[0].0;
        let mut portal_right = &portals[0].1;

        path.push(portal_apex.to_owned());

        let mut i = 1;
        while i < portals.len() {
            let Some(portal) = portals.get(i) else {
                break;
            };
            let left = &portal.0;
            let right = &portal.1;

            if Self::triangle_area2(portal_apex, portal_right, right) <= 0.0 {
                if portal_apex == portal_right
                    || Self::triangle_area2(portal_apex, portal_left, right) > 0.0
                {
                    portal_right = right;
                    right_index = i;
                } else {
                    portal_apex = portal_left;
                    let apex_index = left_index;
                    path.push(portal_apex.to_owned());

                    portal_left = portal_apex;
                    portal_right = portal_apex;
                    left_index = apex_index;
                    right_index = apex_index;

                    i = apex_index + 1;
                    continue;
                }
            }

            if Self::triangle_area2(portal_apex, portal_left, left) >= 0.0 {
                if portal_apex == portal_left
                    || Self::triangle_area2(portal_apex, portal_right, left) < 0.0
                {
                    portal_left = left;
                    left_index = i;
                } else {
                    portal_apex = portal_right;
                    let apex_index = right_index;
                    path.push(portal_apex.to_owned());

                    portal_left = portal_apex;
                    portal_right = portal_apex;
                    left_index = apex_index;
                    right_index = apex_index;

                    i = apex_index + 1;
                    continue;
                }
            }

            i += 1;
        }

        let Some(last_portal) = portals.get(portals.len() - 1) else {
            return path;
        };
        let last_portal = last_portal.0;
        let Some(final_path) = path.get(path.len() - 1) else {
            return path;
        };
        if !f64_eq(final_path.x, last_portal.x) || !f64_eq(final_path.y, last_portal.y) {
            path.push(last_portal.into());
        }

        path
    }

    pub fn native_nearest_valid_point_with_move_dir(
        &self,
        point: &F64Point,
        move_dir: &F64Point,
    ) -> Option<F64Point> {
        let target_point = F64Point::new(point.x + move_dir.x, point.y + move_dir.y);
        if self.get_polygon_at_point(&target_point).is_some() {
            return Some(target_point);
        }
    
        // 获取点所在的多边形
        let Some(polygon_id) = self.get_polygon_at_point(point) else { return None; };
        let Some(polygon_info) = self.data.polygons.get(polygon_id) else { return None; };
        let points: Vec<F64Point> = polygon_info
            .point_indices
            .iter()
            .map(|&v| self.data.points[v].to_owned())
            .collect();
    
        // 初始化变量
        let mut closest_point = None;
        let mut min_distance = f64::MAX;
        let mut edge_slide_point = None;
        let mut slide_distance = f64::MAX;
    
        for i in 0..points.len() {
            let current_point = &points[i];
            let next_point = &points[(i + 1) % points.len()];
    
            // 计算边的向量和长度
            let edge_vector = F64Point::new(
                next_point.x - current_point.x,
                next_point.y - current_point.y,
            );
            let edge_length_squared = edge_vector.x * edge_vector.x + edge_vector.y * edge_vector.y;
            let edge_length = edge_length_squared.sqrt();
    
            // 检查边长度是否为零，避免除以零
            if edge_length == 0.0 {
                continue;
            }
    
            // 归一化边的单位向量
            let edge_unit_vector = F64Point::new(
                edge_vector.x / edge_length,
                edge_vector.y / edge_length,
            );
    
            // 计算投影比例，确保投影点在边上
            let t = ((target_point.x - current_point.x) * edge_vector.x
                + (target_point.y - current_point.y) * edge_vector.y)
                / edge_length_squared;
            let clamped_t = t.clamp(0.0, 1.0);
    
            // 计算投影点
            let projected_point = F64Point::new(
                current_point.x + clamped_t * edge_vector.x,
                current_point.y + clamped_t * edge_vector.y,
            );
    
            // 计算目标点到投影点的距离平方
            let distance_squared = (target_point.x - projected_point.x).powi(2)
                + (target_point.y - projected_point.y).powi(2);
    
            // 更新最近的投影点
            if distance_squared < min_distance {
                min_distance = distance_squared;
                closest_point = Some(projected_point);
            }
    
            // 计算移动向量在边方向上的投影长度
            let move_vector = F64Point::new(move_dir.x, move_dir.y);
            let projected_length = move_vector.x * edge_unit_vector.x + move_vector.y * edge_unit_vector.y;
    
            // 如果投影长度大于零，表示移动方向与边方向的夹角小于90度
            if projected_length > 0.0 {
                // 将投影长度限制在边的长度范围内
                let clamped_projected_length = projected_length.clamp(0.0, edge_length);
    
                // 计算沿边滑动的点
                let slide_point = F64Point::new(
                    point.x + edge_unit_vector.x * clamped_projected_length,
                    point.y + edge_unit_vector.y * clamped_projected_length,
                );
    
                // 计算滑动距离的平方
                let slide_distance_squared = (point.x - slide_point.x).powi(2)
                    + (point.y - slide_point.y).powi(2);
    
                // 更新最近的滑动点
                if slide_distance_squared < slide_distance {
                    slide_distance = slide_distance_squared;
                    edge_slide_point = Some(slide_point);
                }
            }
        }
    
        // 如果找到沿边滑动的点，则返回该点
        if let Some(slide_point) = edge_slide_point {
            return Some(slide_point);
        }
    
        // 否则返回最近的投影点
        closest_point
    }

    pub fn search_path_with_radius(
        &self,
        start: &F64Point,
        end: &F64Point,
        radius: f64,
        max_points: usize
    ) -> Option<Vec<F64Point>> {
        let base_path = self.search_path_smooth(start, end)?;
        if base_path.len() < 3 {
            return Some(base_path);
        }

        let mut cache = LruCache::new(NonZeroUsize::new(128).unwrap());
        let mut result = Vec::with_capacity(base_path.len() * 2);
        result.push(base_path[0].clone());

        for i in 1..base_path.len() - 1 {
            let prev = &base_path[i - 1];
            let curr = &base_path[i];
            let next = &base_path[i + 1];

            let arc_points = self.generate_corner_arc_with_cache(
                prev, curr, next, radius, max_points, &mut cache
            );

            if let Some(points) = arc_points {
                result.extend(points);
            } else {
                result.push(curr.clone());
            }
        }

        result.push(base_path.last().unwrap().clone());
        Some(self.simplify_path(result, radius))
        // Some(result)
    }

    fn generate_corner_arc_with_cache(
        &self,
        prev: &F64Point,
        curr: &F64Point,
        next: &F64Point,
        radius: f64,
        max_points: usize,
        cache: &mut LruCache<(EqF64, EqF64, EqF64), Cow<'static, Vec<F64Point>>>
    ) -> Option<Vec<F64Point>> {
        let key = (
            EqF64::new(prev.x, prev.y),
            EqF64::new(curr.x, curr.y),
            EqF64::new(next.x, next.y)
        );
        
        if let Some(cached) = cache.get(&key) {
            return Some(cached.to_vec());
        }

        let arc_points = self.generate_corner_arc(prev, curr, next, radius, max_points);
        if let Some(points) = &arc_points {
            cache.put(key, Cow::Owned(points.clone()));
        }
        arc_points
    }

    fn generate_corner_arc(
        &self,
        prev: &F64Point,
        curr: &F64Point,
        next: &F64Point,
        radius: f64,
        max_points: usize
    ) -> Option<Vec<F64Point>> {
        // 计算方向向量
        let in_vec = F64Point::new(curr.x - prev.x, curr.y - prev.y);
        let out_vec = F64Point::new(next.x - curr.x, next.y - curr.y);
        
        // 计算向量长度
        let in_len = in_vec.length();
        let out_len = out_vec.length();
        if in_len < f64::EPSILON || out_len < f64::EPSILON {
            return None;
        }

        // 计算夹角
        let angle = in_vec.angle_between(&out_vec);
        if !(MIN_ANGLE..=MAX_ANGLE).contains(&angle) {
            return None;
        }

        // 计算实际可用半径
        let safe_radius = self.calculate_safe_radius(curr, &in_vec, &out_vec, radius);
        if safe_radius < radius * 0.5 {
            return None;
        }

        // 计算圆心
        let (center, start_angle, sweep_angle) = self.calculate_arc_center(
            prev, curr, next, safe_radius
        )?;

        // 生成圆弧点
        let mut arc_points = self.generate_arc_points(
            &center, safe_radius, start_angle, sweep_angle, max_points
        );

        // 有效性过滤
        arc_points.retain(|p| self.is_point_valid(p, safe_radius));
        if arc_points.len() < 2 {
            return None;
        }

        Some(arc_points)
    }

    fn calculate_safe_radius(
        &self,
        curr: &F64Point,
        in_vec: &F64Point,
        out_vec: &F64Point,
        desired_radius: f64
    ) -> f64 {
        let in_normalized = in_vec.normalized();
        let out_normalized = out_vec.normalized();
        let bisector = self.normalize(&(&in_normalized + &out_normalized));
        let max_check = desired_radius * 2.0;
        
        // 沿角平分线方向检测
        let test_point = F64Point::new(
            curr.x + bisector.x * max_check,
            curr.y + bisector.y * max_check
        );
        
        if self.get_polygon_at_point(&test_point).is_some() {
            desired_radius
        } else {
            self.binary_search_radius(curr, &bisector, desired_radius)
        }
    }

    fn binary_search_radius(
        &self,
        curr: &F64Point, 
        direction: &F64Point,
        max_radius: f64
    ) -> f64 {
        let mut low = 0.0;
        let mut high = max_radius;
        let mut best = 0.0;

        for _ in 0..5 {
            let mid = (low + high) / 2.0;
            let test_point = F64Point::new(
                curr.x + direction.x * mid,
                curr.y + direction.y * mid
            );
            
            if self.get_polygon_at_point(&test_point).is_some() {
                best = mid;
                low = mid;
            } else {
                high = mid;
            }
        }
        best * (1.0 - SAFETY_MARGIN)
    }

    fn calculate_arc_center(
        &self,
        prev: &F64Point,
        curr: &F64Point,
        next: &F64Point,
        radius: f64
    ) -> Option<(F64Point, f64, f64)> {
        // 计算内角平分线方向
        let in_dir = self.normalize(&F64Point::new(curr.x - prev.x, curr.y - prev.y));
        let out_dir = self.normalize(&F64Point::new(next.x - curr.x, next.y - curr.y));
        let bisector = self.normalize(&(in_dir + out_dir));

        // 计算夹角
        let angle = in_dir.angle_between(&out_dir);
        
        // 处理钝角、直角和外凸角的情况
        let center_dist = if angle >= PI {
            // 钝角或外凸角，使用较小的半径
            radius * 1.5
        } else if angle >= PI / 2.0 {
            // 直角，使用较大的半径
            radius * 2.0
        } else {
            // 锐角，使用标准计算
            radius / (angle / 2.0).sin()
        };
        
        // 计算圆心坐标
        let center = F64Point::new(
            curr.x + bisector.x * center_dist,
            curr.y + bisector.y * center_dist
        );

        // 计算起始角度和扫描角度
        let start_angle = (-out_dir.y).atan2(-out_dir.x);
        let sweep_angle = if angle >= PI {
            // 钝角或外凸角，使用较小的扫描角度
            angle * 0.5
        } else {
            PI - angle
        };

        Some((center, start_angle, sweep_angle))
    }

    fn generate_arc_points(
        &self,
        center: &F64Point,
        radius: f64,
        start_angle: f64,
        sweep_angle: f64,
        max_points: usize
    ) -> Vec<F64Point> {
        let step = sweep_angle / (max_points as f64 - 1.0);
        (0..max_points)
            .map(|i| {
                let angle = start_angle + step * i as f64;
                F64Point::new(
                    center.x + radius * angle.cos(),
                    center.y + radius * angle.sin()
                )
            })
            .collect()
    }

    fn is_point_valid(&self, p: &F64Point, radius: f64) -> bool {
        self.get_polygon_at_point(p).is_some() &&
        self.check_clearance(p, radius)
    }

    fn check_clearance(&self, p: &F64Point, radius: f64) -> bool {
        let test_points = [
            F64Point::new(p.x + radius, p.y),
            F64Point::new(p.x - radius, p.y),
            F64Point::new(p.x, p.y + radius),
            F64Point::new(p.x, p.y - radius)
        ];
        
        test_points.iter()
            .all(|tp| self.get_polygon_at_point(tp).is_some())
    }

    fn simplify_path(&self, path: Vec<F64Point>, radius: f64) -> Vec<F64Point> {
        let mut simplified = Vec::new();
        let mut iter = path.iter().peekable();

        while let Some(curr) = iter.next() {
            simplified.push(curr.clone());
            
            while let Some(next) = iter.peek() {
                if self.line_of_sight(curr, next, radius) {
                    iter.next();
                } else {
                    break;
                }
            }
        }
        simplified
    }

    fn line_of_sight(&self, a: &F64Point, b: &F64Point, radius: f64) -> bool {
        let distance = a.distance(b);
        if distance < f64::EPSILON {
            return true;
        }
        
        // 修正采样逻辑
        let min_step = radius * 0.5;
        let max_steps = 10;
        let step_count = ((distance / min_step).ceil() as usize).min(max_steps);
        let step_size = 1.0 / step_count as f64;
        
        (0..=step_count).all(|i| {
            let t = i as f64 * step_size;
            let p = F64Point::new(
                a.x + (b.x - a.x) * t,
                a.y + (b.y - a.y) * t
            );
            self.is_point_valid(&p, radius)
        })
    }

    fn normalize(&self, v: &F64Point) -> F64Point {
        let len = v.length();
        if len > 0.0 {
            F64Point::new(v.x / len, v.y / len)
        } else {
            v.clone()
        }
    }
}

#[inline]
fn f64_eq(a: f64, b: f64) -> bool {
    (a - b).abs() < f64::EPSILON
}

// 判断点是否在凸多边形内
fn is_point_in_convex_polygon(point: &F64Point, polygon: &[F64Point]) -> bool {
    let mut last_cross_product = None;

    for i in 0..polygon.len() {
        let a = &polygon[i];
        let b = &polygon[(i + 1) % polygon.len()];

        // 向量 AB 和 AP 的叉乘
        let ab = F64Point::new(b.x - a.x, b.y - a.y);
        let ap = F64Point::new(point.x - a.x, point.y - a.y);
        let cross_product = ab.x * ap.y - ab.y * ap.x;

        if let Some(last_cp) = last_cross_product {
            // 检查叉乘的符号是否一致
            if cross_product * last_cp < 0.0 {
                return false;
            }
        }
        last_cross_product = Some(cross_product);
    }
    true
}

// 计算点到线段的最近点
fn nearest_point_on_segment(p: &F64Point, a: &F64Point, b: &F64Point) -> F64Point {
    let ab = F64Point::new(b.x - a.x, b.y - a.y);
    let ap = F64Point::new(p.x - a.x, p.y - a.y);

    let ab_len_squared = ab.x * ab.x + ab.y * ab.y;
    let t = ((ap.x * ab.x + ap.y * ab.y) / ab_len_squared).clamp(0.0, 1.0);

    F64Point::new(a.x + t * ab.x, a.y + t * ab.y)
}

// 获取点在凸多边形中的最近点
fn get_nearest_point_in_convex_polygon(point: &F64Point, polygon: &[F64Point]) -> (F64Point, f64) {
    if is_point_in_convex_polygon(point, polygon) {
        return (point.to_owned(), 0f64);
    }

    let mut nearest_point = polygon[0];
    let mut min_distance = f64::MAX;

    for i in 0..polygon.len() {
        let a = &polygon[i];
        let b = &polygon[(i + 1) % polygon.len()];
        let candidate_point = nearest_point_on_segment(point, a, b);
        let distance = point.distance_2(&candidate_point);

        if distance < min_distance {
            min_distance = distance;
            nearest_point = candidate_point;
        }
    }

    (nearest_point, min_distance)
}
